/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

/**
 *
 * @author QuangHieu
 */
class Node{
    int data;
    Node next;

    Node(int x){
        data=x;
        next=null;
    }
    Node(int x, Node t){
        data=x;
        next=t;
    }
}
class Queue {

    Node head,tail;

    Queue(){
        head=tail=null;
    }

    boolean EmptyS(){
        return head==tail;
    }

    void addQ(int x){
        Node t=new Node(x);
        if(head==null)head=tail=t;
        else {
            tail.next=t;
            tail=t;
        }
    }

    int RemoveQ(){
        if(head==null){
            System.out.print("\nQueue rong!\n");
            return -1;
        }
        else {
            int x=head.data;
            if(head==tail) head=tail=null;
            else head=head.next;
            return x;
        }
    }

    void daoQ(){
        int m[]=new int[100];
        int i=0;
        while(!this.EmptyS()){
            m[i]=this.RemoveQ();
            i++;
        }
        for(int j=i-1;j>=0;j--)
            this.addQ(m[j]);
    }

    // sap xep
    void RadixSort(int []a){
        Queue QQ=new Queue();
        int max=a[1];
        Queue[]q=new Queue[10];
        for(int j=0;j<=9;j++)
            q[j]=new Queue();
        for(int i=1;i<=a.length;i++){
            QQ.addQ(a[i]);
            if(a[i]>max)
                max=a[i];
        }
        int k=String.valueOf(max).length();
        int gt=1,x;
        for(int i=1;i<=k;i++){
            while(!QQ.EmptyS()){
                x=QQ.RemoveQ();
                int vt=(x/gt)%10;
                q[vt].addQ(x);
            }
            for(int j=0;j<=9;j++)
                while(!q[j].EmptyS())
                    QQ.addQ(q[j].RemoveQ());
            gt=gt*10;
        }
        for(int i=1;i<a.length;i++)
            a[i]=QQ.RemoveQ();
    }
    public static void main(String args[]){
        Queue q=new Queue();
        /*
        for(int i=1;i<=10;i++)
            q.addQ(i);
        q.daoQ();
        while(!q.EmptyS())
            System.out.print(" "+ q.RemoveQ());
         */
        int a[]=new int[100];
        for(int i=1;i<20;i++)
            a[i]=(int)((Math.random())*1000);
        q.RadixSort(a);
        for(int i=1;i<20;i++)
            System.out.print("\n"+a[i]+"\t");
        System.out.println();

    }
}
